LeetCode 51、N 皇后

一、题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解释：4 皇后问题存在两个不同的解法。

二、题目解析

三、参考代码

1、Java 代码

class Solution {

    // 保存所有符合要求的解
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
      
      // attack 用来表示皇后的攻击范围
      int[][] attack = new int[n][n];
      // queen 用来记录皇后的位置
      char[][] queen = new char[n][n];

      // 初始化二维数组 queen 中所有的元素为 '.'
      for(char[] c : queen) {
         Arrays.fill(c, '.');
      }

      // 初始化二维数组 attack 中所有的元素为 0
      // 0 代表没有皇后能攻击得到
      // 1 代表出于任意一个皇后的攻击范围内
      for(int[] c : attack) {
          Arrays.fill(c, 0);
      }

      // 从棋盘的第 0 行第 0 列处理 n 皇后的情况
      backtrack(0,n,queen,attack);

      // 最后，返回所有符合要求的解
      return res;
    }

    // 很显然，每一行只能放置一个皇后，所以我们每一行每一行的来放置皇后
    // k 表示当前处理的行
    // n 表示需要放置多少个皇后，同时也代表棋盘的大小为 n * n
    // queen 用来记录皇后的位置
    // attack 用来表示皇后的攻击范围
    private void backtrack(int k ,int n , char[][] queen,int[][] attack){

        // 如果发现在棋盘的最后一行放置好了皇后，那么就说明找到了一组符合要求的解
        if(k == n){
            // 由于 queen 为二维字符数组，所以需要转换为字符串数组
            List<String> list = new ArrayList<>();
            // 遍历二维数组 queen
            // 取出 queen 的每一行字符数组 c
            for (char[] c : queen) {
                // 把字符数组 c 中的所有字符转换为字符串的形式进行拼凑
                // 比如 ['.','Q','.','.',]
                // 转换为 '.Q..'
                // 把这个字符串加入到 list 中
                list.add(String.copyValueOf(c));
            }

            // list 即为一组符合要求的解，把它加入到结果数组中
            res.add(list);
            // 由于遍历完了所有的行，无需再遍历下去，所以返回
            return;
        }

        // 每一行只能放置一个皇后
        // 并且每一列也只能放置一个皇后
        // 所以在 k 行中，从 0 列到 n - 1 列，判断皇后应该放置到哪个位置
        for(int i = 0 ; i < n ; i++){
            // 如果发现 attack[k][i] == 0
            // 说明这个位置不在任何一个皇后的攻击范围内
            // 所以可以考虑放置皇后
            if(attack[k][i] == 0){

                // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了
                // 由于有可能在( k , i )  位置放置了皇后之后，在后续的其它行会无法再放置其它的皇后
                // 那么就需要回到 ( k , i )  的状态，考虑能不能在 ( k , i + 1 )的位置放置
                // 为了能够回到 ( k , i )  的状态，所以需要先记录此时的 attack
                // 使用一个临时的二维数组，深度拷贝 attack
                // 如果不使用深度拷贝，而是直接使用 int[][] temp = c
                // 会导致 attack 发生改变是 temp 也会发生改变
                // 这样也就无法保存之前的状态了
                int[][] temp = new int[n][n];
                
                // 通过两个 for 循环，把 attack 中的所有元素深度拷贝到 temp
                for(int l = 0 ; l < n ; l++){
                    for( int m = 0 ; m < n ; m++){
                        temp[l][m] = attack[l][m];
                    }
                }

                // queen 用来记录皇后的位置
                // 那么 ( k , i )  的位置 queen[k][i] = 'Q'
                queen[k][i] = 'Q';

                // 由于新放置了一个皇后，所以攻击范围又更多了
                // 所以需要更新 attack 数组
                // 新放置皇后的坐标为 ( k , i ) ，同样的需要更新它的八个方向
                checkQueenAttack(k,i,attack);
                
                // 如果在 ( k , i )  位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后
                // 递归的调用 backtrack 在 k + 1 行放置皇后
                backtrack(k + 1,n,queen,attack);
                
                // 递归结束后，拿走皇后，恢复 attack 的状态，考虑能不能在 ( k ,i + 1 )的位置放置
                attack = temp;

                // 恢复 queen 的状态，说明此时皇后不放置在( k , i )  位置
                queen[k][i] = '.';
            }
        }


    }

    // 坐标 ( x , y) 为皇后所处的位置
    // 更新 attack
    private void checkQueenAttack(int x ,int y,int[][] attack){

        // 对于每一个坐标 (x,y) 来说，都有上、下、左、右、左上、左下、右上、右下 八个方向
        //【左上】的坐标为 (x - 1, y - 1)
        //【上】的坐标为 (x - 1, y )
        //【右上】的坐标为 (x - 1, y + 1)
        //【左】的坐标为 (x, y + 1)
        //【右】的坐标为 (x , y - 1)
        //【左下】的坐标为 (x + 1, y - 1)
        //【下】的坐标为 (x + 1, y)
        //【右下】的坐标为 (x + 1, y + 1)
        // 通过两个一维数组可以表示这八个方向
        // dx 表示 x 的方向
        int dx[] = { -1 , -1 , -1 , 0  ,  0 ,  1  , 1 , 1 };
        // dy 表示 y 的方向
        int dy[] = { -1 , 0  , 1 , -1 ,  1 ,  -1 , 0 , 1 };

        // 皇后所处的坐标肯定是皇后能攻击的位置，设置为 1
        attack[x][y] = 1;

        // 以坐标 ( x , y) 为中心，去更新它八个方向的坐标
        for(int j = 0 ; j < 8; j++){
            // 由内向外的进行更新
            for(int i = 1 ; i < attack.length ; i++){
                // 新的位置的坐标行为 x + i * dx[j]
                int nx = x + i * dx[j];
                // 新的位置的坐标列为 y + i * dy[j]
                int ny = y + i * dy[j];

                // 如果新位置的坐标在 n * n 的棋盘范围内
                if(nx >= 0 && nx < attack.length && ny >= 0 && ny < attack.length){
                    // 那么这些位置就是在坐标为 （x，y）的皇后的攻击范围内，更新为 1
                    attack[nx][ny] = 1;
                }

            }
        }
    }
}

**2、**C++ 代码

class Solution {
       // 保存所有符合要求的解
       vector<vector<string>> res;
public:
    vector<vector<string>> solveNQueens(int n) {

      
      // attack 用来表示皇后的攻击范围
      vector<vector<int>> attack(n,vector<int>(n));

      for( int i = 0 ; i < n ; i++){
          for(int j = 0 ; j < n ; j++){
              attack[i][j] = 0;
          }
      }

      // queen 用来记录皇后的位置
      vector<vector<string>> queen(n,vector<string>(n));

      for( int i = 0 ; i < n ; i++){
          for(int j = 0 ; j < n ; j++){
              queen[i][j] = ".";
          }
      }

      // 从棋盘的第 0 行第 0 列处理 n 皇后的情况
      backtrack(0,n,queen,attack);

      // 最后，返回所有符合要求的解
      return res;
    }

    // 很显然，每一行只能放置一个皇后，所以我们每一行每一行的来放置皇后
    // k 表示当前处理的行
    // n 表示需要放置多少个皇后，同时也代表棋盘的大小为 n * n
    // queen 用来记录皇后的位置
    // attack 用来表示皇后的攻击范围
    void backtrack(int k, int n , vector<vector<string>> &queen,vector<vector<int>> &attack){

        // 如果发现在棋盘的最后一行放置好了皇后，那么就说明找到了一组符合要求的解
        if(k == n){

            vector<string> ans = {};

            for(int i = 0 ; i < n ; i++){

                string temp = "";

                for( int j = 0 ; j < n ; j++){

                    temp += queen[i][j];

                }

                ans.push_back(temp);
            }

           
            res.push_back(ans);

            // 由于遍历完了所有的行，无需再遍历下去，所以返回
            return;
        }

        // 每一行只能放置一个皇后
        // 并且每一列也只能放置一个皇后
        // 所以在 k 行中，从 0 列到 n - 1 列，判断皇后应该放置到哪个位置
        for(int i = 0 ; i < n ; i++){
            // 如果发现 attack[k][i] == 0
            // 说明这个位置不在任何一个皇后的攻击范围内
            // 所以可以考虑放置皇后
            if(attack[k][i] == 0){

                // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了
                // 由于有可能在( k , i )  位置放置了皇后之后，在后续的其它行会无法再放置其它的皇后
                // 那么就需要回到 ( k , i )  的状态，考虑能不能在 ( k , i + 1 )的位置放置
                // 为了能够回到 ( k , i )  的状态，所以需要先记录此时的 attack
                // 使用一个临时的二维数组，深度拷贝 attack
                // 如果不使用深度拷贝，而是直接使用 int[][] temp = c
                // 会导致 attack 发生改变是 temp 也会发生改变
                // 这样也就无法保存之前的状态了
                vector<vector<int>> temp(n,vector<int>(n));

                
                // 通过两个 for 循环，把 attack 中的所有元素深度拷贝到 temp
                for(int l = 0 ; l < n ; l++){
                    for( int m = 0 ; m < n ; m++){
                        temp[l][m] = attack[l][m];
                    }
                }

                // queen 用来记录皇后的位置
                // 那么 ( k , i )  的位置 queen[k][i] = 'Q'
                queen[k][i] = 'Q';

                // 由于新放置了一个皇后，所以攻击范围又更多了
                // 所以需要更新 attack 数组
                // 新放置皇后的坐标为 ( k , i ) ，同样的需要更新它的八个方向
                checkQueenAttack(k,i,attack);
                
                // 如果在 ( k , i )  位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后
                // 递归的调用 backtrack 在 k + 1 行放置皇后
                backtrack(k + 1,n,queen,attack);
                
                // 递归结束后，拿走皇后，恢复 attack 的状态，考虑能不能在 ( k ,i + 1 )的位置放置
                attack = temp;

                // 恢复 queen 的状态，说明此时皇后不放置在( k , i )  位置
                queen[k][i] = '.';
            }
        }


    }

    // 坐标 ( x , y) 为皇后所处的位置
    // 更新 attack
    void checkQueenAttack(int x ,int y, vector<vector<int>> &attack){

        // 对于每一个坐标 (x,y) 来说，都有上、下、左、右、左上、左下、右上、右下 八个方向
        //【左上】的坐标为 (x - 1, y - 1)
        //【上】的坐标为 (x - 1, y )
        //【右上】的坐标为 (x - 1, y + 1)
        //【左】的坐标为 (x, y + 1)
        //【右】的坐标为 (x , y - 1)
        //【左下】的坐标为 (x + 1, y - 1)
        //【下】的坐标为 (x + 1, y)
        //【右下】的坐标为 (x + 1, y + 1)
        // 通过两个一维数组可以表示这八个方向
        // dx 表示 x 的方向
        int dx[8] = { -1 , -1 , -1 , 0  ,  0 ,  1  , 1 , 1 };
        // dy 表示 y 的方向
        int dy[8] = { -1 , 0  , 1 , -1 ,  1 ,  -1 , 0 , 1 };

        // 皇后所处的坐标肯定是皇后能攻击的位置，设置为 1
        attack[x][y] = 1;

        // 以坐标 ( x , y) 为中心，去更新它八个方向的坐标
        for(int j = 0 ; j < 8; j++){
            // 由内向外的进行更新
            for(int i = 1 ; i < attack.size() ; i++){
                // 新的位置的坐标行为 x + i * dx[j]
                int nx = x + i * dx[j];
                // 新的位置的坐标列为 y + i * dy[j]
                int ny = y + i * dy[j];

                // 如果新位置的坐标在 n * n 的棋盘范围内
                if(nx >= 0 && nx < attack.size() && ny >= 0 && ny < attack.size()){
                    // 那么这些位置就是在坐标为 （x，y）的皇后的攻击范围内，更新为 1
                    attack[nx][ny] = 1;
                }

            }
        }
    }
};

3、Python 代码

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 更新皇后的坐标[x][y]之后更新attack的位置
        def updateAttack(x,y,attack):
            # 更改attack[x][y]上、下、左、右、左上、左下、右上、右下的0为1
            # dx表示x的方向，dy表示y的方向
            dx = [-1, -1, 1, 0, 0, 1, 1, 1]
            dy = [-1, 0, 1, -1, 1, -1, 0, 1]
            # 八个方向更新
            for j in range(8):
                # 内到外更新
                for i in range(n):
                    nx = x + i * dx[j]
                    ny = y + i * dy[j]
                    # 新坐标在棋盘内则更新
                    if nx >= 0 and nx < n and ny >= 0 and ny < n:
                        attack[nx][ny] = 1

        # k为当前处理的行
        # n表示需要放置的皇后数和棋盘大小
        # queen皇后的位置
        # attack攻击范围
        def backtrack(k,n,queen,attack):
            print(k)
            # 如果棋盘最后一行放置好了皇后则找到一组解
            if k == n:
                rl = []
                # queen为分隔的二维数组，去转为字符串数组
                for i in queen:
                    rl.append(''.join(i))
                res.append(rl)
                return
            
            # 每行每列只能放一个皇后，所以在k行中，从0～n-1列判断皇后放置的位置
            for i in range(n):
   
                # 如果attack[k][i]为0，即不在攻击范围内，可考虑放置皇后
                if attack[k][i] == 0:
                    # k行i列放置后需考虑k+1行如何放置
                    # 若k+1无法放置，需回退，考虑k行i+1列能否放置
                    # 用临时数组记录k行i列时的attack状态
                    # temp = attack[:]
                    # 要使用深度拷贝
                    temp =  copy.deepcopy(attack)

                    queen[k][i] = 'Q'
                    # 更新attack数组
                    updateAttack(k,i,attack)
                    # print(attack,queen,'after')
                    # 递归的调用backtrack考虑在k+1行放置皇后
                    backtrack(k+1,n,queen,attack)

                    # 递归结束移走皇后恢复[k][i]不能放置状态
                    attack = temp
                    # print(attack,3)
                    # 恢复queen状态
                    queen[k][i] = '.'
        
        res = []
        # attack表示皇后攻击范围
        # 初始化攻击为0 
        '''0表示没有皇后能攻击得到，1表示处于任意一个皇后的攻击范围内'''
        attack = []
        for i in range(n):
            attack.append([0] * n)
        # queen记录皇后位置
        # 初始化queen所有元素为'.'
        queen = []
        for i in range(n):
            queen.append(['.'] * n)
        # 从棋盘的第0行第0列处理n皇后情况
        backtrack(0, n, queen, attack)
        # 返回结果
        return res